package com.example.demo.algorithm.tree.b_add_tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

/**
 * @author: htc
 * @date: Created in 13:41 2018/12/11.
 */
public class Node {
    /**
     * 是否为叶子节点
     */
    protected boolean isLeaf;

    /**
     * 是否为根节点
     */
    protected boolean isRoot;

    /**
     * 父节点
     */
    protected Node parent;

    /**
     * 叶节点的前节点
     */
    protected Node previous;

    /**
     * 叶节点的后节点
     */
    protected Node next;

    /**
     * 节点的关键字
     */
    protected List<Map.Entry<Comparable, Object>> entries;

    /**
     * 子节点
     */
    protected List<Node> children;

    public Node(boolean isLeaf) {
        this.isLeaf = isLeaf;
        entries = new ArrayList<Map.Entry<Comparable, Object>>();
        if (!isLeaf) {
            children = new ArrayList<Node>();
        }
    }

    public Node(boolean isLeaf, boolean isRoot) {
        this(isLeaf);
        this.isRoot = isRoot;
    }

    public Object get(Comparable key) {
        //如果是叶子节点
        if (isLeaf) {
            for (Map.Entry<Comparable, Object> entry : this.entries) {
                if (entry.getKey().compareTo(key) == 0) {
                    return entry.getValue();
                }
            }
        } else {
            //如果不是叶子节点

            //如果key小于等于节点最左边的key，沿第一个子节点继续搜索
            if (key.compareTo(entries.get(0)) <= 0) {
                return children.get(0).get(key);
            } else if (key.compareTo(entries.get(entries.size() - 1).getKey()) >= 0) {
                //如果key大于节点最右边的key，沿最后一个子节点继续搜索
                return children.get(children.size() - 1).get(key);
            } else {
                //否则沿比key大的前一个子节点继续搜索
                for (int i = 0; i < entries.size(); i++) {
                    if (entries.get(i).getKey().compareTo(key) <= 0
                            && entries.get(i + 1).getKey().compareTo(key) > 0) {
                        return children.get(i).get(key);
                    }
                }
            }
        }
        return null;
    }

    public void insertOrUpdate(Comparable key, Object obj, BPlusTree tree){

    }
}
